#define _CRT_SECURE_NO_WARNINGS 1

//#include<stdio.h>
//#include<math.h>
//
//int main()
//{
//	int i = 0, j = 0, x = 0;
//	scanf("%d", &x);
//	for (i = 1; i <= x; i++)
//	{
//		for (j = 2; j <= sqrt(i); j++)
//		{
//			if (i % j == 0)
//				break;
//		}
//		if (j > sqrt(i))
//			printf("%d ", i);
//	}
//	return 0;
//}

//struct ListNode* removeElements(struct ListNode* head, int val)
//{
//    if (head == NULL)
//        return head;
//    struct ListNode* prev = NULL, * tail = head;
//    while (tail)
//    {
//        struct ListNode* Next = tail->next;
//        if (tail->val == val)
//        {
//            if (prev == NULL)
//            {
//                head = Next;
//                tail = Next;
//            }
//            else
//            {
//                prev->next = Next;
//                free(tail);
//                tail = Next;
//            }
//        }
//        else
//        {
//            prev = tail;
//            tail = Next;
//        }
//    }
//    return head;
//}


//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* n1 = NULL, * n2 = head;
//    if (head == NULL)
//        return head;
//    while (n2)
//    {
//        struct ListNode* n3 = n2->next;
//        n2->next = n1;
//        n1 = n2;
//        n2 = n3;
//    }
//    return n1;
//}


//struct ListNode* middleNode(struct ListNode* head)
//{
//    struct ListNode* slow = head, * fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//    }
//    return slow;
//}

//struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
//    // write code here
//    struct ListNode* slow = pListHead, * fast = pListHead;
//    while (k--)
//    {
//        if (fast == NULL)
//        {
//            return NULL;
//        }
//        fast = fast->next;
//    }
//    while (fast)
//    {
//        slow = slow->next;
//        fast = fast->next;
//    }
//    return slow;
//}
//
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
//{
//    if (list1 == NULL)
//        return list2;
//    if (list2 == NULL)
//        return list1;
//    struct ListNode* head = NULL;
//    struct ListNode* tail = NULL;
//    while (list1 && list2)
//    {
//        if ((list1->val) < (list2->val))
//        {
//            if (tail == NULL)
//            {
//                head = list1;
//                tail = list1;
//            }
//            else
//            {
//                tail->next = list1;
//                tail = list1;
//            }
//            list1 = list1->next;
//        }
//        else
//        {
//            if (tail == NULL)
//            {
//                head = list2;
//                tail = list2;
//            }
//            else
//            {
//                tail->next = list2;
//                tail = list2;
//            }
//            list2 = list2->next;
//        }
//    }
//    if (list1)
//        tail->next = list1;
//    if (list2)
//        tail->next = list2;
//    return head;
//}

struct ListNode* MidNode(struct ListNode* Head)
{
    struct ListNode* slow = Head, * fast = Head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

struct ListNode* RevNode(struct ListNode* Head)
{
    struct ListNode* prev = NULL, * cur = Head;
    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* B = MidNode(A);
        B = RevNode(B);
        while (A && B)
        {
            if (A->val == B->val)
            {
                A = A->next;
                B = B->next;
            }
            else {
                return false;
            }
        }
        return true;
    }
};